
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param map int整型二维数组 代表地图的二维数组
     * @param a_x int整型 小 A 出生点的 x 坐标
     * @param a_y int整型 小 A 出生点的 y 坐标
     * @param b_x int整型 小 B 出生点的 x 坐标
     * @param b_y int整型 小 B 出生点的 y 坐标
     * @return int整型
     */
    boolean[][] flag;
    int min = Integer.MAX_VALUE;
    private int[][] dir = {{0,1}, {0, -1}, {1,0}, {-1, 0}};
    private void getWay(int[][] map, int a_x, int a_y, int b_x, int b_y, int count) {
        if (map[a_x][a_y] == 0) {
            return;
        }
        if (a_x == b_x && a_y == b_y) {
            min = Math.min(min, count);
            return;
        }
        for(int i = 0; i < 4; i++) {
            int a_xx = a_x + dir[i][0];
            int a_yy = a_y + dir[i][1];
            if (a_xx >= 0 && a_xx < map.length && a_yy >= 0 && a_yy < map[0].length && !flag[a_xx][a_yy]) {
                flag[a_xx][a_yy] = true;
                getWay(map, a_xx, a_yy, b_x, b_y, count+1);
                flag[a_xx][a_yy] = false;
            }
        }
        return;
    }
    public int getEstTime (int[][] map, int a_x, int a_y, int b_x, int b_y) {
        // write code here
        flag = new boolean[map.length][map[0].length];
        getWay(map, a_x, a_y, b_x, b_y, 0);
        return (min) / 2;

    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.min);
        int[][] arr = {{1, 1, 1, 0, 1}, {1, 0, 1, 1, 1}, {1, 1, 1, 0, 1}, {0, 0, 1, 1, 1}, {1, 0, 0, 0, 1}};
        int res = solution.getEstTime(arr,0,0,4,4);
        System.out.println(res);
    }
}
//[[1, 1, 1, 0, 1], [1, 0, 1, 1, 1], [1, 1, 1, 0, 1], [0, 0, 1, 1, 1], [1, 0, 0, 0, 1]],0,0,4,4